//package com.klun.tree.binaryTree;
//
//import java.util.HashMap;
//import java.util.LinkedHashMap;
//
//class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//    TreeNode<K,V> parent;  // red-black tree links
//    TreeNode<K,V> left;
//    TreeNode<K,V> right;
//    TreeNode<K,V> prev;    // needed to unlink next upon deletion
//    boolean red;
//    TreeNode(int hash, K key, V val, HashMap.Node<K,V> next) {
//        super(hash, key, val, next);
//    }
//
//    /**
//     * Returns root of tree containing this node.
//     */
//    final TreeNode<K,V> root() {
//        for (TreeNode<K,V> r = this, p;;) {
//            if ((p = r.parent) == null)
//                return r;
//            r = p;
//        }
//    }
//
//    /**
//     * Ensures that the given root is the first node of its bin.
//     */
//    static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
//        int n;
//        if (root != null && tab != null && (n = tab.length) > 0) {
//            int index = (n - 1) & root.hash;
//            HashMap.TreeNode<K,V> first = (HashMap.TreeNode<K,V>)tab[index];
//            if (root != first) {
//                HashMap.Node<K,V> rn;
//                tab[index] = root;
//                HashMap.TreeNode<K,V> rp = root.prev;
//                if ((rn = root.next) != null)
//                    ((HashMap.TreeNode<K,V>)rn).prev = rp;
//                if (rp != null)
//                    rp.next = rn;
//                if (first != null)
//                    first.prev = root;
//                root.next = first;
//                root.prev = null;
//            }
//            assert checkInvariants(root);
//        }
//    }
//
//    /**
//     * Finds the node starting at root p with the given hash and key.
//     * The kc argument caches comparableClassFor(key) upon first use
//     * comparing keys.
//     */
//    final HashMap.TreeNode<K,V> find(int h, Object k, Class<?> kc) {
//        HashMap.TreeNode<K,V> p = this;
//        do {
//            int ph, dir; K pk;
//            HashMap.TreeNode<K,V> pl = p.left, pr = p.right, q;
//            if ((ph = p.hash) > h)
//                p = pl;
//            else if (ph < h)
//                p = pr;
//            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
//                return p;
//            else if (pl == null)
//                p = pr;
//            else if (pr == null)
//                p = pl;
//            else if ((kc != null ||
//                    (kc = comparableClassFor(k)) != null) &&
//                    (dir = compareComparables(kc, k, pk)) != 0)
//                p = (dir < 0) ? pl : pr;
//            else if ((q = pr.find(h, k, kc)) != null)
//                return q;
//            else
//                p = pl;
//        } while (p != null);
//        return null;
//    }